class Solution {
    /**
     * 费波纳泰数
     * https://leetcode.cn/problems/n-th-tribonacci-number/description/
     * @param n
     * @return
     */
    public static int fib(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;

        //1，状态表示dp【i】表示第i个斐波那契数
        //2.状态转移方程 dp[i] = dp[i -1] + dp[i -2];

        //3.初始化和填表
        int[] dp = new int[n + 1];
        dp[0] = 0;dp[1] = 1;
        for(int i = 2;i < n + 1;i++){
            dp[i] = (dp[i -1] + dp[i -2]) % (int)(1e9 + 7);
        }


        return dp[n];
    }

    /**
     * 三步问题
     * https://leetcode.cn/problems/three-steps-problem-lcci/description/
     * @param n
     * @return
     */
    public int waysToStep(int n) {

        long a = 1,b = 2,c = 4,sum = 0;

        for(int i = 0;i < n - 1;i++){
            sum = (a + b + c) % 1000000007;
            a = b;
            b = c;
            c = sum;
        }

        return (int)a;
    }

    /**
     * 最小爬楼梯费用
     * https://leetcode.cn/problems/min-cost-climbing-stairs/
     * @param cost
     * @return
     */
        public int minCostClimbingStairs(int[] cost) {
            int n = cost.length;

            //1.状态表示dp[i]表示到i台阶的最小费用
            //2.状态转移方程
            //dp[i] = Math.min(dp[i-1] + cost[i-1],dp[i-2] + cost[i-2])

            //3.初始化
            int[] dp = new int[n + 1];
            dp[0] = 0;dp[1] = 0;

            //4.填表
            for(int i = 2;i <= n;i++){
                dp[i] = Math.min(dp[i-1] + cost[i-1],dp[i-2] + cost[i-2]);
            }

            return dp[n];
        }

}
